package cn.michael.dev.data.structure.linked.list;


import cn.michael.dev.entity.ListNode;

/**
 * Created by hufenggang on 2021/8/20.
 *
 * 问题描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 */
public class Leetcode61 {

    public ListNode rotateRight1(ListNode head, int k) {

        while (k > 0) {

            if (head == null || head.next == null) {
                return head;
            }

            ListNode currentNode = head;
            ListNode lastNode = head.next;

            while(lastNode.next != null) {
                currentNode = currentNode.next;
                lastNode = lastNode.next;
            }

            currentNode.next = null;
            lastNode.next = head;

            head = lastNode;
            k--;
        }

        return head;
    }

    /**
     * 解题思路：闭合为环
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {

        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        // 计算链表的大小
        int n = 1;
        ListNode currentNode = head;
        while (currentNode.next != null) {
            currentNode = currentNode.next;
            n++;
        }

        int add = n - k % n;
        if (add == n) {
            return head;
        }

        // 构建环型链表
        currentNode.next = head;
        while (add-- > 0) {
            currentNode = currentNode.next;
        }

        ListNode result = currentNode.next;
        currentNode.next = null;
        return result;
    }
}
